package com.cwj.lab3.博客需要.TopoSort;

import com.cwj.lab1.LinkStack;
import com.cwj.lab1.QueueCy;
import com.cwj.lab1.myArrayList;
import com.cwj.lab3.博客需要.Graph_table_2;

public class TopoSort_2 {
    Graph_table_2 graph;//邻接表
    LinkStack<Integer> DFS_sta;//用来存储DFS实现的拓扑排序的结果
    QueueCy<Integer>BFS_que;//用来存储BFS实现的拓扑排序的结果

    public TopoSort_2(Graph_table_2 graph) {
        this.graph = graph;
        DFS_sta=null;
    }
/**
 * DFS实现
 * @return 即没有一个结点入度为0，那么就返回false,否则为true;
 */
    public boolean SortDFS(){
        boolean[]vis=new boolean[this.graph.getV_num()];
        LinkStack<Integer> sta=new LinkStack<>();
        myArrayList<Graph_table_2.Node>list=this.graph.getNodeList();
        for (int i = 0; i < list.size(); i++) {
            if(list.get(i).getInDegree()==0){
                this.SortDFS(i,vis,sta);
                this.DFS_sta=sta;
                return true;
            }
        }

        return false;
    }
    private void SortDFS(int ind, boolean[]vis, LinkStack<Integer> sta){
        int to=0;
        myArrayList<Graph_table_2.Edge>list=graph.getNodeList().get(ind).getEdgeList();
        vis[ind]=true;
        for (int i = 0; i <list.size() ; i++) {
            to=list.get(i).getTo();
            if(!vis[to]){
                SortDFS(to,vis,sta);
            }
        }
        sta.push(ind);
    }
/**
 * BFS实现的拓扑排序
 * */
    public void SortBFS(){
        myArrayList<Graph_table_2.Node>list=this.graph.getNodeList();
        this.BFS_que=new QueueCy<>();
        QueueCy<Integer>que=new QueueCy<>();
        for (int i = 0; i < list.size(); i++) {
            if(list.get(i).getInDegree()==0){
                que.push(i);
            }
        }
        int top=0,to=0;
        Graph_table_2.Node nn=null;
        while(!que.isEmpty()){
            this.BFS_que.push(top=que.pop());
            myArrayList<Graph_table_2.Edge>edgeList=this.graph.getNodeList().get(top).getEdgeList();
            for (int i = 0; i <edgeList.size() ; i++) {
                nn=list.get(to=edgeList.get(i).getTo());
                nn.setInDegree(nn.getInDegree()-1);
                if(nn.getInDegree()==0){
                    que.push(to);
                }
            }
        }
    }

    public QueueCy<Integer> getBFS_que() {
        return BFS_que;
    }

    public LinkStack<Integer> getDFS_sta() {
        return DFS_sta;
    }

    public static void main(String[] args) {
        String path="src/src/com/cwj/lab3/TopSort_data";
        Graph_table_2 graph=new Graph_table_2();
        graph.init_undirect(path,false);
        TopoSort_2 topo=new TopoSort_2(graph);
        System.out.println("DFS_TopSort:");
        topo.SortDFS();
        topo.getDFS_sta().show();
        System.out.println();
        System.out.println("BFS_TopSort:");
        topo.SortBFS();
        topo.getBFS_que().show();

    }
}

//DFS_TopSort:
//{0 1 7 2 5 8 3 4 6 9 10 12 11 }
//BFS_TopSort:
//{0 1 3 2 7 4 5 6 8 9 10 11 12 }